//==============================================================================
//
//          DBitArray - the bit array data type in the ofc-library
//
//               Copyright (C) 2003  Dick van Oudheusden
//  
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 3 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this library; if not, write to the Free
// Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
//
//==============================================================================
// 
//  $Date: 2008-07-19 12:28:59 $ $Revision: 1.10 $
//
//==============================================================================

#include "ofc/DBitArray.h"

#include <limits.h>
#include <string.h>

#if _INTERFACE_

#include "ofc/config.h"

//
// The bit array data type implements a number of methods for creating, 
// manipulating and checking bit sets. 
//
// @example
//
// #include <stdio.h>
// #include "ofc/DBitArray.h"
// 
// int main(int argc, char *argv[])
// {
//   DBitArray *array = [DBitArray alloc];
// 
//   [array init :1 :25];         // Initialise the array for values from 1..25
// 
//   [array set   :7];            // Set value 7 in the array
//   [array set   :9 :20];        // Set values 9..20 in the array
//   [array reset :11];           // Reset value 11 in the array
//   [array reset :15 :18];       // Reset values 15..18 in the array
// 
//                                // Checking values
//   printf("Value 10 is %s\n", [array has :10] ? "set" : "reset");
//   printf("Value  8 is %s\n", [array has :8 ] ? "set" : "reset");
// 
//   printf("Threre are %d values set\n", [array count]);
// 
//   [array free];                // Cleanup
// 
//   return 0;
// }
// 

@interface DBitArray : DObject
{
@private
  unsigned char *_array;  // the bits for the array
  int            _min;    // the minimum value in the bit array
  int            _max;    // the maximum value in the bit array
  int            _size;   // the size of the bit array
}

#endif


@implementation DBitArray

//// Constructors

//
// Initialise to an empty bit array with range 0..255
//
// @return the object
//

- (DBitArray *) init
{
  [self init :0 :255];

  return self;
}

//
// Initialise to an empty bit array
//
// @param min      the minimum value in the bit array
// @param max      the maximum value in the bit array
//
// @return the object
//

- (DBitArray *) init :(int) min :(int) max
{
  [super init];

  if (min > max)
  {
    WARNING(DW_ARG_OUT_RANGE, "min");
    min = max;
  }
    
  _min = min;
  _max = max;

  _size = (_max - _min + 1);
  _size = (_size % CHAR_BIT == 0) ? _size / CHAR_BIT : _size / CHAR_BIT + 1;
  
  _array = (unsigned char *) objc_malloc(sizeof(unsigned char) * _size);

  [self reset];

  return self;
}



//// Copy related methods

//
// Do a shallow copy of the object
//
// @return the object
//
- shallowCopy
{
  DBitArray *copy = [super shallowCopy];
  
  copy->_array = (unsigned char *) objc_malloc(sizeof(unsigned char) * _size);
  
  memcpy(copy->_array, _array, sizeof(unsigned char) * _size);
  
  return copy;
}


//// Destructor

//
// Free the bit array
//
// @return the object
//

- free
{
  objc_free(_array);
  
  [super free];

  return self;
}


//// Member methods

//
// Return the minimum value in the bit array
//
// @return the minumum value
//

- (int) min
{
  return _min;
}

//
// Return the maximum value in the bit array
//
// @return the maximum value
//

- (int) max
{
  return _max;
}



//// Main methods

//
// Set one value in the bit array
//
// @param val       the value to set
//
// @return the object
//

- (DBitArray *) set :(int) val
{
  if ((val >= _min) && (val <= _max))
  {
    int off = val - _min;
    int ind = off / CHAR_BIT;
    int bit = off % CHAR_BIT;

    _array[ind] = _array[ind] | (1 << bit);
  }
  else
    WARNING(DW_ARG_OUT_RANGE, "val");
  
  return self;
}

//
// Set a range of values in the bit array
//
// @param from     the start of the bit array (incl.)
// @param to       the end of the bit array (incl.)
//
// @return the object
//

- (DBitArray *) set :(int) from :(int) to
{
  from = (from < _min) ? 0           : from - _min;
  to   = (to   > _max) ? _max - _min : to   - _min;

  while (from <= to)
  {
    _array[from / CHAR_BIT] |= (1 << (from % CHAR_BIT));

    from++;
  }

  return self;
}

//
// Set a range of values, stepwise in the bit array
//
// @param from     the start of the bit set (incl.)
// @param to       the end of the bit set (incl.)
// @param step     the step for the bit set (> 0)
//
// @return the object
//

- (DBitArray *) set :(int) from :(int) to :(unsigned) step
{
  if (step > 0)
  {
    from = (from < _min) ? 0           : from - _min;
    to   = (to   > _max) ? _max - _min : to   - _min;

    while (from <= to)
    {
      _array[from / CHAR_BIT] |= (1 << (from % CHAR_BIT));

       from += step;
    }
  }
  else
    WARNING(DW_INVALID_ARG, "step");

  return self;
}

//
// Reset the whole bit array
//
// @return the object
//

- (DBitArray *) reset
{
  memset(_array, 0, sizeof(unsigned char) * _size);

  return self;
}

//
// Reset one value in the bit array
//
// @param val       the value to reset
//
// @return the object
//

- (DBitArray *) reset :(int) val
{
  if ((val >= _min) && (val <= _max))
  {
    int off = val - _min;

    _array[off / CHAR_BIT] &= (~(1 << (off % CHAR_BIT)));
  }
  else
    WARNING(DW_ARG_OUT_RANGE, "val");
    
  return self;
}

//
// Reset a range of values in the bit array
//
// @param from     the start of the bit set (incl.)
// @param to       the end of the bit set (incl.)
//
// @return the object
//

- (DBitArray *) reset :(int) from :(int) to
{
  from = (from < _min) ? 0           : from - _min;
  to   = (to   > _max) ? _max - _min : to   - _min;

  while (from <= to)
  {
    _array[from / CHAR_BIT] &= (~(1 << (from % CHAR_BIT)));

    from++;
  }

  return self;
}

//
// Reset a range of values, stepwise in the bit array
//
// @param from     the start of the bit set (incl.)
// @param to       the end of the bit set (incl.)
// @param step     the step for the bit set (> 0)
//
// @return the object
//

- (DBitArray *) reset :(int) from :(int) to :(unsigned) step
{
  if (step > 0)
  {
    from = (from < _min) ? 0           : from - _min;
    to   = (to   > _max) ? _max - _min : to   - _min;

    while (from <= to)
    {
      _array[from / CHAR_BIT] &= (~(1 << (from % CHAR_BIT)));

       from += step;
    }
  }
  else
    WARNING(DW_INVALID_ARG, "step");

  return self;
}


//// Checking methods

//
// Check if a value is set in the bit array
//
// @param val      the value to be checked
//
// @return is the value set in the bit array ?
//

- (BOOL) has :(int) val
{
  BOOL found = NO;
  
  if ((val >= _min) && (val <= _max))
  {
    int off = val - _min;

    found = ((_array[off / CHAR_BIT] & (1 << (off % CHAR_BIT))) != 0);
  }
  else
    WARNING(DW_ARG_OUT_RANGE, "val");
      
  return found;
}

//
// Count the number of values set
//
// @return the number of values set
//

- (int) count 
{
  int cnt = 0;
  int min = 0;
  int max = _max - _min;

  while (min <= max)
  {
    if (_array[min / CHAR_BIT] & (1 << (min % CHAR_BIT)))
      cnt++;

    min++;
  }

  return cnt;  
}

@end

/*==========================================================================*/
